package lc;
import java.util.*;

public class Ex146 {
    class LRUCache {
        DoubleList cache;
        Map<Integer, Node> map;
        int capacity;

        public LRUCache(int capacity) {
            cache = new DoubleList();
            map = new HashMap<>();
            this.capacity = capacity;
        }
        
        public int get(int key) {
            if (!map.containsKey(key)) return -1;
            Node node = map.get(key);
            cache.remove(node);
            cache.addFirst(node);
            return node.v;
        }
        
        public void put(int key, int value) {
            if (!map.containsKey(key)) {
                Node node = new Node(key, value);
                if (cache.size() == capacity) {
                    Node n = cache.removeLast();
                    map.remove(n.k);
                }
                cache.addFirst(node);
                map.put(key, node);
            } else {
                Node node = map.get(key);
                node.v = value;
                cache.remove(node);
                cache.addFirst(node);
            }
        }

        class DoubleList {

            Node head, tail;
            int size;

            public DoubleList() {

                head = tail = new Node(-1, -1);
                head.next = tail;
                tail.prev = head;
                size = 0;
            }

            public void addFirst(Node node) {
                node.next = head.next;
                node.prev = head;
                head.next.prev = node;
                head.next = node;
                size++;
            }

            public void remove(Node node) {
                node.prev.next = node.next;
                node.next.prev = node.prev;
                size--;
            }

            public Node removeLast() {
                Node node = tail.next;
                tail.prev = node.prev;
                node.prev.next = tail;
                size--;
                return node;
            }

            public int size() {
                return size;
            }
        }

        class Node {
            Node prev, next;
            int k, v;

            public Node(int k, int v) {
                this.k = k;
                this.v = v;
            }
        }
    }
    
}
